// 版权2019 etcd作者
// 
// 根据Apache许可证2.0版（以下简称“许可证”）获得许可；
// 除非遵守许可证，否则不得使用此文件。
// 您可以通过
// 
// www.apache.org/licenses/LICENSE-2.0 
// 
// 除非适用法律要求或书面同意，否则根据许可证分发的软件
// 按“原样”分发，
// 无任何明示或暗示的保证或条件。
// 请参阅许可证，了解管理许可的特定语言和
// 许可证下的限制。

package tracker

import (
	"fmt"
	"sort"
	"strings"

	"go.etcd.io/etcd/raft/v3/quorum"
	pb "go.etcd.io/etcd/raft/v3/raftpb"
)

// Config反映在ProgressTracker中跟踪的配置。
type Config struct {
	Voters quorum.JointConfig
	// 如果配置是联合的，则自动离开为真，并且当
	// 可能时，应通过Raft自动执行传入配置。如果为false，则在
	// 应用程序手动启动转换之前，配置将是联合的。
	AutoLeave bool
	// 学习者是一组ID，对应于当前配置中活动的学习者。
	// 
	// 不变量：学习者和投票者不相交，即如果一个同伴在
	// 联合配置的任何一半中，它都不能是学习者；如果是
	// 学习者，则不能在关节配置的任何一半中。这个不变的
	// 简化了实现，因为它允许对等方清楚了解
	// 其当前角色，而不考虑联合共识。
	Learners map[uint64]struct{}
	// 当我们在联合共识过渡期间将选民转变为学习者时，
	// 我们不能在进入联合状态时直接添加学习者。这是
	// 因为这违反了
	// 选民和学习者的交集为空的不变量。例如，假设一个投票者被删除，并且立即重新添加为学习者（或者换句话说，它被降级）：
	// 
	// 最初，配置为
	// 
	// 投票者：{1 2 3}
	// 学习者：{}
	// 
	// 我们想降级3。进入联合配置，我们天真地得到
	// 
	// 投票者：{12}&{12}
	// 学习者：{3}
	// 
	// 但这违反了不变量（3既是投票者又是学习者）。相反，我们得到了
	// 
	// 选民：{12}&{12}
	// 学习者：{}
	// 下一个学习者：{3}
	// 
	// 其中3现在仍然是纯粹的选民，但是我们记住了在转换到最终配置时使其成为学习者的意图：
	// 
	// 投票人：{12}
	// 学习者：{3}
	// 下一个学习者：{}
	// 
	// 请注意，在添加非
	// 的学习者时，不会使用next_学习者，该学习者也是联合配置中的投票人。在这种情况下，学习者在进入关节配置时立即添加
	// 以便尽快赶上
	// 的进度。
	LearnersNext map[uint64]struct{}
}

func (c Config) String() string {
	var buf strings.Builder
	fmt.Fprintf(&buf, "voters=%s", c.Voters)
	if c.Learners != nil {
		fmt.Fprintf(&buf, " learners=%s", quorum.MajorityConfig(c.Learners).String())
	}
	if c.LearnersNext != nil {
		fmt.Fprintf(&buf, " learners_next=%s", quorum.MajorityConfig(c.LearnersNext).String())
	}
	if c.AutoLeave {
		fmt.Fprintf(&buf, " autoleave")
	}
	return buf.String()
}

// Clone返回配置的副本，该副本与原始配置不共享内存。
func (c *Config) Clone() Config {
	clone := func(m map[uint64]struct{}) map[uint64]struct{} {
		if m == nil {
			return nil
		}
		mm := make(map[uint64]struct{}, len(m))
		for k := range m {
			mm[k] = struct{}{}
		}
		return mm
	}
	return Config{
		Voters:       quorum.JointConfig{clone(c.Voters[0]), clone(c.Voters[1])},
		Learners:     clone(c.Learners),
		LearnersNext: clone(c.LearnersNext),
	}
}

// ProgressTracker跟踪当前活动的配置以及其中节点和学习者的已知信息
// 。特别是，它跟踪每个对等方的匹配
// 索引，从而允许对提交的索引进行推理。
type ProgressTracker struct {
	Config

	Progress ProgressMap

	Votes map[uint64]bool

	MaxInflight int
}

// MakeProgressTracker初始化ProgressTracker。
func MakeProgressTracker(maxInflight int) ProgressTracker {
	p := ProgressTracker{
		MaxInflight: maxInflight,
		Config: Config{
			Voters: quorum.JointConfig{
				quorum.MajorityConfig{},
				nil, // 仅在使用时填充
			},
			Learners:     nil, // 仅在使用时填充
			LearnersNext: nil, // 仅在使用时填充
		},
		Votes:    map[uint64]bool{},
		Progress: map[uint64]*Progress{},
	}
	return p
}

// ConfState返回表示活动配置的ConfState。
func (p *ProgressTracker) ConfState() pb.ConfState {
	return pb.ConfState{
		Voters:         p.Voters[0].Slice(),
		VotersOutgoing: p.Voters[1].Slice(),
		Learners:       quorum.MajorityConfig(p.Learners).Slice(),
		LearnersNext:   quorum.MajorityConfig(p.LearnersNext).Slice(),
		AutoLeave:      p.AutoLeave,
	}
}

// IsSingleton在当前配置中只有一个投票成员
// （即领先者）时返回true。
func (p *ProgressTracker) IsSingleton() bool {
	return len(p.Voters[0]) == 1 && len(p.Voters[1]) == 0
}

type matchAckIndexer map[uint64]*Progress

var _ quorum.AckedIndexer = matchAckIndexer(nil)

// AckedIndex实现IndexLookuper。
func (l matchAckIndexer) AckedIndex(id uint64) (quorum.Index, bool) {
	pr, ok := l[id]
	if !ok {
		return 0, false
	}
	return quorum.Index(pr.Match), true
}

// Committed返回已知的最大日志索引，该索引基于
// 该组有投票权的成员所确认的内容。
func (p *ProgressTracker) Committed() uint64 {
	return uint64(p.Voters.CommittedIndex(matchAckIndexer(p.Progress)))
}

func insertionSort(sl []uint64) {
	a, b := 0, len(sl)
	for i := a + 1; i < b; i++ {
		for j := i; j > a && sl[j] < sl[j-1]; j-- {
			sl[j], sl[j-1] = sl[j-1], sl[j]
		}
	}
}

// 检测连通数量
func (p *ProgressTracker) Visit(f func(id uint64, pr *Progress)) {
	n := len(p.Progress)
	var sl [7]uint64
	var ids []uint64
	if len(sl) >= n {
		ids = sl[:n]
	} else {
		ids = make([]uint64, n)
	}
	for id := range p.Progress {
		n--
		ids[n] = id
	}
	insertionSort(ids)
	for _, id := range ids {
		f(id, p.Progress[id])
	}
}

// 检测当前集群中与当前Leader节点连通的节点个数是否超过了半数
func (p *ProgressTracker) QuorumActive() bool {
	votes := map[uint64]bool{}
	p.Visit(func(id uint64, pr *Progress) {
		if pr.IsLearner {
			return
		}
		votes[id] = pr.RecentActive
	})

	return p.Voters.VoteResult(votes) == quorum.VoteWon
}

// VoterNodes将选出一部分选民。
func (p *ProgressTracker) VoterNodes() []uint64 {
	m := p.Voters.IDs()
	nodes := make([]uint64, 0, len(m))
	for id := range m {
		nodes = append(nodes, id)
	}
	sort.Slice(nodes, func(i, j int) bool { return nodes[i] < nodes[j] })
	return nodes
}

// LearnerNodes返回已排序的学习者片段。
func (p *ProgressTracker) LearnerNodes() []uint64 {
	if len(p.Learners) == 0 {
		return nil
	}
	nodes := make([]uint64, 0, len(p.Learners))
	for id := range p.Learners {
		nodes = append(nodes, id)
	}
	sort.Slice(nodes, func(i, j int) bool { return nodes[i] < nodes[j] })
	return nodes
}

// ResetVotes通过recordVote为新一轮计票做准备。
func (p *ProgressTracker) ResetVotes() {
	p.Votes = map[uint64]bool{}
}

// 将收到的投票结果记录到raft.votes字段中，之后通过统计该字段从而确定该节点的得票数
func (p *ProgressTracker) RecordVote(id uint64, v bool) {
	_, ok := p.Votes[id]	// 记录集群中其他节点的投票结采
	if !ok {
		p.Votes[id] = v
	}
}

// TallyVotes返回被批准和被拒绝的票数，以及
// 选举结果是否已知。
// 统计投票结果并返回
func (p *ProgressTracker) TallyVotes() (granted int, rejected int, _ quorum.VoteResult) {
	for id, pr := range p.Progress {
		if pr.IsLearner {
			continue
		}
		v, voted := p.Votes[id]
		if !voted {
			continue
		}
		if v {
			granted++
		} else {
			rejected++
		}
	}
	result := p.Voters.VoteResult(p.Votes)
	return granted, rejected, result
}
